Question: Given a prime $p$ and an integer $a$, we say that $a$ is a $\textit{primitive root} \pmod p$ if the set $\{a,a^2,a^3,\ldots,a^{p-1}\}$ contains exactly one element congruent to each of $1,2,3,\ldots,p-1\pmod p$.

For example, $2$ is a primitive root $\pmod 5$ because $\{2,2^2,2^3,2^4\}\equiv \{2,4,3,1\}\pmod 5$, and this list contains every residue from $1$ to $4$ exactly once.

However, $4$ is not a primitive root $\pmod 5$ because $\{4,4^2,4^3,4^4\}\equiv\{4,1,4,1\}\pmod 5$, and this list does not contain every residue from $1$ to $4$ exactly once.

What is the sum of all integers in the set $\{1,2,3,4,5,6\}$ that are primitive roots $\pmod 7$?
Solution: Obviously, $1$ is not a primitive root $\pmod 7$ (its powers are all congruent to $1$!).

Examining the powers of $2$, we see that $\{2^1,2^2,2^3,2^4,\ldots\} \equiv \{2,4,1,2,\ldots\}$ with repetition from this point onward. Since the powers of $2$ do not include all residues from $1$ to $6\pmod 7$, we see that $2$ is not a primitive root.

The logic of this example can be generalized. If $a$ is an integer and $a^k\equiv 1\pmod p$, then the powers of $a$ repeat on a cycle of length at most $k$. Therefore, for $a$ to be a primitive root, it is necessary that $a^k\not\equiv 1\pmod p$ for all positive $k$ smaller than $p-1$. Conversely, if $a^k\equiv 1\pmod p$ for some positive $k$ smaller than $p-1$, then $a$ is not a primitive root $\pmod p$. As examples, $4$ and $6$ are not primitive roots $\pmod 7$, because $4^3\equiv 1\pmod 7$ and $6^2\equiv 1\pmod 7$.

This leaves $3$ and $5$ as candidates. Checking the powers of $3$ and $5$ modulo $7$, we see that \begin{align*}
3^1\equiv 3,~ 3^2\equiv 2,~3^3 \equiv 6,~3^4\equiv 4,~3^5\equiv 5,~ 3^6\equiv 1;\\
5^1\equiv 5,~ 5^2\equiv 4,~5^3 \equiv 6,~5^4\equiv 2,~5^5\equiv 3,~ 5^6\equiv 1.\,
\end{align*}Thus, $3,5$ are primitive roots of $7$, so the desired sum is $3+5=\boxed{8}$.